package code.class3;

/**
 * https://leetcode.cn/problems/first-missing-positive/
 * 缺失的第一个正数问题
 * <p>
 * *[-3,2,1,8,5,4,2,3,5,13]
 * *[ 0 1 2 3 4 5 6 7 8 9 ] 10
 * *  L                     R
 * *  L:左边都是做到i+1在i位置
 * *  R:1.垃圾区域
 * *    2.如果最好状态 1-r,每个数能全
 * 情况1：arr[l] == l+1,l++
 * 情况2：arr[l] <= l 垃圾
 * 情况3：arr[l] > r 垃圾
 * 情况4：arr[arr[l]-1] == arr[l],垃圾
 * 情况5：交换
 */
public class Code09_firstMissingPositive {
    public static void main(String[] args) {
        int[] arr = {-3, 2, 1, 8, 5, 4, 2, 3, 5, 13};
        int ans = firstMissingPositive(arr);
        System.out.println("ans = " + ans);
    }

    public static int firstMissingPositive(int[] arr) {
        int l = 0, r = arr.length;
        while (l < r) {
            // 下标与数值匹配
            if (arr[l] == l + 1) {
                l++;
                // 当 查到的数据都为垃圾数据时，交换位置
            } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                swap(arr, l, --r);
            } else {
                // 当不为垃圾数据时，与正确位置互换
                swap(arr, l, arr[l] - 1);
            }
        }
        return l + 1;
    }

    public static void swap(int[] arr, int x, int y) {
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }
}
